package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * leetcode 77. 组合
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/14 18:21
 */
public class E77 {
    /*
       例如求n = 4 , k = 2 的组合，组合为：一共6 种：C(4,2) = 6
              1        2     3     4
            / | \     / \    |     X
           2  3  4   3  4    4

      又例如求 n = 6 , k = 3 的组合，组合为： 一共 20 种： C(6,3) = 20
                       1                                    2                           3             4          5           6
             /      |      |     |   \           /      |      |    \             /     |    \        |          |           X
            2       3      4     5    6         3       4      5    6            4      5     6       5          6
         / | | \  / | \   / \    |    X       / | \    / \     |    X           / \     |     X       |          X
        3  4 5 6 4  5  6 5  6    6           4  5 6   5  6     6                5  6    6             6
     */

    /**
     * 组合
     * @param n n
     * @param k k
     * @return 所有组合
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(1, result, new LinkedList<>(), n, k);
        return result;
    }

    /**
     * 递归求解
     * 一次递归表示处理当前位置，而一次递归里面的for循环代表这次递归也就是这个位置有可能的数字，对比上面的树就知道了
     * @param start 开始位置
     * @param result 结果集
     * @param currentCombine 当前组合
     * @param n n
     * @param k k
     */
    private void dfs(int start,
                     List<List<Integer>> result,
                     LinkedList<Integer> currentCombine,
                     int n,
                     int k) {
        // 递归终止条件：当前组合的长度等于k
        if (currentCombine.size() == k){
            result.add(new ArrayList<>(currentCombine));
            return;
        }
        // 依次尝试start - n之间的每一个
        for (int i = start; i <= n; i++){
            // 剪枝，一些不满足条件的分支剪掉
            if (n - i + 1 + currentCombine.size() < k) continue;
            currentCombine.push(i); // 添加当前找到的
            dfs(i + 1, result, currentCombine, n, k); // 继续找下一个，组合不能吃回头草，所以用i+1
            currentCombine.pop(); // 回溯
        }
    }
}
